//
// Created by kero-ly on 2020/6/13.
//
#include "ly_sort.h"

vector<int> LySort::bubbleSort(vector<int> &v) {
    // 1. 适当检查输入
    if (v.size() <= 1)
        return v;

    // 2. 两层循环，i循环代表冒泡的次数，j循环代表第i次冒泡需要交换j次
    vector<int> out = v;
    for (int i=0; i<v.size(); ++i) {
        // 3. 优化的终止条件，若某次冒泡没有改变元素顺序，则排列已经有序，可以结束
        int stop_flag = 1;
        for (int j=0; j<v.size()-i-1; ++j) {
            // 4. 在冒泡过程中，是前后元素(j, j+1)之间的交换，在某次冒泡结束后，最大/最小的元素一定位于最后
            //    因此每一次j循环的次数会比上一次减少1次（也即是-i）
            if (out[j] > out[j+1]) { // increase
                std::swap(out[j], out[j+1]);
                stop_flag = 0;
            }
        }
        if (stop_flag)
            break;
    }
    return out;
}
